// https://leetcode.cn/problems/flood-fill/

// 题干：有一幅以 m x n 的二维整数数组表示的图画 image ，其中 image[i][j] 表示该图画的像素值大小。
//       你也被给予三个整数 sr ,  sc 和 newColor 。你应该从像素 image[sr][sc] 开始对图像进行 上色填充 。
//       为了完成 上色工作 ，从初始像素开始，记录初始坐标的 上下左右四个方向上 像素值与初始坐标相同的相连像素点，
//       接着再记录这四个方向上符合条件的像素点与他们对应 四个方向上 像素值与初始坐标相同的相连像素点，……，
//       重复该过程。将所有有记录的像素点的颜色值改为 newColor 。
//       最后返回 经过上色渲染后的图像 。

// 示例：输入: image = [[1,1,1],[1,1,0],[1,0,1]]，sr = 1, sc = 1, newColor = 2
//       输出: [[2,2,2],[2,2,0],[2,0,1]]

// 碎语：floodfill算法，本质上是找一个性质相同的连通块
//       遍历所有元素，当找到一个符合条件的元素后，进行dfs/bfs搜索，直到不能再搜索

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    bool vis[51][51];
    int m, n;
    int target;
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color)
    {
        m = image.size(), n = image[0].size();
        target = image[sr][sc], image[sr][sc] = color;
        memset(vis, 0, sizeof(vis));
        vis[sr][sc] = true;

        dfs(image, sr, sc, color);

        return image;
    }

    int dx[4] = {-1,1,0,0};
    int dy[4] = {0,0,-1,1};

    void dfs(vector<vector<int>>& image, int i, int j, int color)
    {
        for (int k = 0 ; k < 4 ; k++){
            int x = i + dx[k], y = j + dy[k];

            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && image[x][y] == target){
                vis[x][y] = true;
                image[x][y] = color;

                dfs(image, x, y, color);
            }
        }
    }
};

int main()
{
    Solution sol;
    vector<vector<int>> image = {{1,1,1},{1,1,0},{1,0,1}};

    sol.floodFill(image, 1, 1, 2);
    for (const auto& arr : image){
        for (const auto& num : arr){
            cout << num << " ";
        }
        cout << endl;
    }

    return 0;
}









